from typing import List
import json


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def genTreeFromStr(listStr: str):
    list = json.loads(listStr)
    if not list:
        return None
    queue = []
    root = TreeNode(list.pop(0))
    queue.append(root)
    t, i = None, 0
    while queue:
        if(i >= len(list)):
            break
        for _ in range(0, len(queue)):
            t = queue.pop(0)
            if t:
                t.left = None if not list[i] else TreeNode(list[i])
                i += 1
                if(i >= len(list)):
                    break
                t.right = None if not list[i] else TreeNode(list[i])
                i += 1
                queue.append(t.left)
                queue.append(t.right)

    return root


def visitTree(root: TreeNode):
    queue = []
    res = []
    queue.append(root)
    while(len(queue) != 0):
        t = queue.pop(0)
        res.append('null' if(t == None) else t.val)
        if(t):
            queue.append(t.left)
            queue.append(t.right)

    for i in range(len(res)-1, -1, -1):
        if(res[i] == 'null'):
            res.pop(i)
        else:
            break
    print(res)


